This lecture introduced the foundational concepts of graphs, formal terminology, and the three standard representations with their storage and operation trade-offs.

  • We saw why graphs matter by looking at real-world examples like social networks, web pages, and road maps, and formalized a graph as a set of vertices and edges, or G=(V,E).
  • We learned core graph terminology, including the differences between undirected vs. directed and unweighted vs. weighted graphs, as well as terms like vertex, edge, degree, in-degree, and out-degree.
  • A key focus was on the three standard representations: the Edge List, Adjacency List, and Adjacency Matrix. We analyzed their space complexity and the performance of common operations for each.
  • We learned about common implementation pitfalls, such as ensuring symmetry in undirected graphs and correctly placing weights in directed graphs.
  • The lecture concluded with a summary of representation trade-offs and a look ahead to the next topic: graph traversal algorithms (BFS & DFS).
  • Key Takeaway: The "best" graph representation depends entirely on the problem. You must choose based on graph density (sparse vs. dense) and which operations need to be fastest.